package com.njupt.DoublePoint;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @Author: wujiaming
 * @CreateTime: 2025/3/6 21:38
 * @Description: 接雨水 42
 * @Version: 1.0
 */


public class Trap_42 {

    /**
     * 暴力法
     * @param height
     * @return
     */
    public int trap1(int[] height) {
        int sum = 0;

        for (int i = 0; i < height.length; i++) {
            if(i == 0 || i == height.length -1) continue;

            int maxLeft = height[i];
            int maxRight = height[i];

            for (int l = i; l >=0 ; l--) {
                if(height[l] > maxLeft){
                    maxLeft = height[l];
                }
            }

            for (int r = i; r <height.length ; r++) {
                if(height[r] > maxRight){
                    maxRight = height[r];
                }
            }

            int h = Math.min(maxLeft,maxRight) - height[i];
            if(h > 0){
                sum += h;
            }
        }
        return sum;
    }

    /**
     * 用动态规划的思想记录当前柱子左边的最大值，以及右边的最大值
     * dp[i] 表示i号柱子左边柱子的最大值
     * @param height
     * @return
     */
    public int trap2(int[] height) {
        int len = height.length;
        int[] dpLeft = new int[len];
        int[] dpRight = new int[len];

        //初始化dp
        dpLeft[0] = height[0];
        for (int i = 1; i < len; i++) {
            dpLeft[i] = Math.max(height[i],dpLeft[i-1]);
        }

        dpRight[len-1] = height[len -1];
        for (int i = len-2; i >=0 ; i--) {
            dpRight[i] = Math.max(height[i],dpRight[i+1]);
        }

        int sum = 0;
        for (int i = 0; i < len; i++) {
            if(i == 0 || i == height.length-1) continue;

            int h = Math.min(dpLeft[i],dpRight[i]) - height[i];
            if(h > 0){
                sum += h;
            }
        }
        return sum;
    }

    /**
     * 采用单调栈的方式
     * @param height
     * @return
     */
    public int trap(int[] height){
        Deque<Integer> stack = new LinkedList<>();
        stack.push(0);
        int sum = 0;
        for (int i = 1; i < height.length; i++) {
            if(height[i] <= height[stack.peek()]){
                stack.push(i);
            }else {
                while(!stack.isEmpty() && height[i] > height[stack.peek()]){
                    int mid = stack.pop();
                    if(!stack.isEmpty()){
                        int h = Math.min(height[stack.peek()],height[i]) - height[mid];
                        int w = i - stack.peek() -1;
                        sum += h * w;
                    }
                }
                stack.push(i);
            }
        }
        return sum;
    }

    public static void main(String[] args) {
        int[] height ={0,1,0,2,1,0,1,3,2,1,2,1};
        Trap_42 test = new Trap_42();
        System.out.println(test.trap(height));
    }
}
